#include "main.h"
#define MAXSTEPS 25  //到终点最多经历几步   
#define MAXSAME 10   //步数一样的点最多有多少
u8 text_col[Y_MAX][X_MAX]={
    {2,2,3,5,4,3,7,4},
    {9,15,12,2,3,12,10,2},
    {1,15,7,13,15,5,15,15},
    {3,12,10,1,14,2,10,10},
    {10,2,10,1,12,10,10,10},
    {10,9,13,7,5,13,13,14},
    {11,7,7,13,4,1,5,14},
    {8,8,9,5,5,5,5,12},
};

struct col{
    u8 x;
    u8 y;
    
};
int step;       //最终需要的步数
struct col step_col[MAXSTEPS];
struct col ke_xi[MAXSTEPS][MAXSAME];
u8 jnum[MAXSTEPS]={0};
//例：ke_xi[2][3] 步数是2的第三个点的坐标



int main(void)
{
    int i,j;
    int flat=0;
    printf("begin!\n");
        ke_xi[0][0].x=0;
        ke_xi[0][0].y=7;
        jnum[0]=1;
        text_col[7][0]|=32;
        
        for(i=1;i<MAXSTEPS;i++){        
            for(j=0;j<jnum[i-1];j++){  //现在普查ke_xi[i-1][j]的关系网络
                    if((text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&1) && !(text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x+1]&32)){//右方有路且未标记
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x+1;
                        //操作下一步的柯西表
                        jnum[i]++;
                        text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x+1]|=32;   //标记
                    }
                    if((text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&2) && !(text_col[ke_xi[i-1][j].y+1][ke_xi[i-1][j].x]&32)){//下方有路且未标记 
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y+1;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x;
                        jnum[i]++;
                        text_col[ke_xi[i-1][j].y+1][ke_xi[i-1][j].x]|=32;   //标记
                    }
                    if((text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&4) && !(text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x-1]&32)){//左方有路且未标记
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x-1;   
                        jnum[i]++;
                        text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x-1]|=32;   //标记
                    }
                    if((text_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&8) && !(text_col[ke_xi[i-1][j].y-1][ke_xi[i-1][j].x]&32)){//上方有路且未标记
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y-1;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x;
                        jnum[i]++;
                        text_col[ke_xi[i-1][j].y-1][ke_xi[i-1][j].x]|=32;   //标记
                        
                    }
                }
        }
    printf("ok\n");
    i=0;
    while(jnum[i++]!=0);
    step=i-2;
    printf("the best step num=%d \n",step);

    for(i=0;i<MAXSTEPS;i++) {
        printf("step=%d ",i);
        for(j=0;j<jnum[i];j++){
            printf("(%d,%d)",ke_xi[i][j].y,ke_xi[i][j].x);
        }
            
        printf("\n");
    }

    printf("the best step is ");


    step_col[step].y=0;
    step_col[step].x=7;
    for(i=step-1;i>=0;i--){
        for(j=0;j<jnum[i];j++){
            flat=0;
            if((abs(ke_xi[i][j].x - step_col[i+1].x)==1&&(ke_xi[i][j].y - step_col[i+1].y==0)) ||
            abs(ke_xi[i][j].y - step_col[i+1].y)==1&&(ke_xi[i][j].x - step_col[i+1].x==0)) {//位置相邻
            //printf("-%d %d %d %d-",ke_xi[i][j].x,step_col[i+1].x,ke_xi[i][j].y,step_col[i+1].y);
                if(ke_xi[i][j].x - step_col[i+1].x==1 && (text_col[step_col[i+1].y][step_col[i+1].x]&1)){//在右侧且没墙
                    flat=1;
                }
                else if(ke_xi[i][j].y - step_col[i+1].y==1 && (text_col[step_col[i+1].y][step_col[i+1].x]&2)){//在下侧且没墙
                    flat=1;
                }
                else if(ke_xi[i][j].x - step_col[i+1].x==-1 && (text_col[step_col[i+1].y][step_col[i+1].x]&4)){//在左侧且没墙
                    flat=1;
                    //printf("f");
                }
                else if(ke_xi[i][j].y - step_col[i+1].y==-1 && (text_col[step_col[i+1].y][step_col[i+1].x]&8)){//在上侧且没墙
                    flat=1;
                }                
                if(flat){
                    step_col[i].x=ke_xi[i][j].x;
                    step_col[i].y=ke_xi[i][j].y;
                    printf("(%d,%d)",step_col[i].y,step_col[i].x);
                    break;
                }
               
            }

        }
    }

    return 0;

}